Práctica 4: Metaheurísticas basadas en poblaciones - Sistemas de Colonias de Hormigas

Lucia Picos Maiztegui

Instrucciones

Esto es Jupyter Notebook, un documento que integra código Python en un archivo Markdown. Esto nos permite ir ejecutando celdas de código poco a poco, así como generar automáticamente un informe bien formateado de la práctica.

Puedes añadir una celda con el botón "Insert" de la barra de herramentas, y cambiar su tipo con "Cell > Cell Type"

Para ejecutar una celda de código, la seleccionaremos y pulsaremos el botón "▶ Run" de la barra de herramentas. Para pasar el documento a HTML, seleccionaremos "File > Download as > HTML (.html)"

Sigue este guión hasta el final. Ejecuta el código proporcionado paso a paso comprendiendo lo que estás haciendo y reflexionando sobre los resultados. Habrá preguntas intercaladas a lo largo del guión, responde a todas ellas en la sección reservada para ese fin: "Respuestas a los cuestionarios". Por favor, no modifiques ninguna linea de código excepto cuando se te pida explícitamente.

No olvides insertar tu nombre y apellidos en la celda superior.

IMPORTANTE: Escribe el código de tu o tus soluciones/respuestas en las celdas que se indican para ello. Además, a lo largo de la práctica se plantearán varias preguntas que debéis responder en la parte inferior del documento, incluyendo las celdas que veáis necesarias (si hacéis referencia a partes concretas de vuestro código, etc) para reponder a ellas.

Entrega de la práctica

La fecha límite de entrega será la indicada en el Campus Virtual. La entrega consistirá de un único archivo comprimido con nombre APELIDOS_NOME_Colonias.zip que contenga los seguientes ficheros:

El Problema del Viajante de Comercio (VC) con Sistemas de Colonias de Hormigas

El objetivo de esta práctica es modelar e implementar un agente inteligente que sea capaz de resolver el problema del VC mediante la metaheurística (MH) de algoritmos para sistemas de colonias de hormigas (ACS, Ant Colony Systems, del inglés).

Para ello, realizarás una implementación del algoritmo básico visto en la clase expositiva y valorarás algunos de los parámetros de diseño del algoritmo en relación a la calidad de las soluciones alcanzadas.

Recuerda que debes importar el módulo Python que acompaña esta práctica, que como ocurría en prácticas anteriores implementa la carga de datos y el cálculo de distancias utilizando una matriz de adyacencia de acuerdo a la definición del problema ya vista.

P4.1: Implementación de Sistemas de Colonias de Hormigas (SCH)

Implementa el algoritmo de sistemas de colonia de hormigas que materializa la MH vista en la sesión expositiva y revisa las notas particulares para el problema de VC. Para facilitar vuestra labor, se os proporciona aquí una descripción algorítmica de referencia.

    1. Establecer parámetros: $G, m, q_{0}, \tau_{0}, \rho, \xi, iter_{min}, iter_{max}, iter_{sinmejoras}, ratio_{mejora}$

    2. Inicializar pistas de feromonas: $\forall (i, j) \tau_{ij} = \tau_{0}$

    3. HACER

        3.1. PARA cada hormiga $k$ en colonia m HACER

            3.1.1.construir una solución para $k$ siguiendo la regla de decisión a cada paso: $$ j=\begin{cases}argmax_{l\in N_i^k} \{ [\tau_{il}]^\alpha [\eta_{il}]^\beta \}, \text{if } q \leq q_0; \\ J, \text{en otro caso;}\end{cases} $$,             donde $J$ es la exploración dirigida por:

$$ p_{ij}^{k} = \frac{[\tau_{ij}]^\alpha [\eta_{ij}]^\beta}{\sum_{l\in N_i^k} [\tau_{il}]^\alpha [\eta_{il}]^\beta}, \text{if } j\in N_i^k $$

            3.1.2. (opcional) Aplicar actualización de feromona local/online con la regla: $$ \tau_{ij} \leftarrow (1 - \xi) \tau_{ij} + \xi \tau_{0}$$

        3.2. FIN PARA

        3.3. Evalúa soluciones en la colonia m y registrar la mejor solución hasta el momento $T^{bs}$

        3.4. Aplicar actualización de feromona global/offline con la regla: $$\tau_{ij} \leftarrow (1-\rho) \tau_{ij} + \rho \Delta\tau_{ij}^{bs}, \forall(i, j) \in T^{bs}$$

    4. HASTA cumplir la condición de parada

La implementación debe permitir la inicialización de los parámetros y estructuras de información asociadas como sigue:

Prueba tu implementación tomando instancias de problemas que has utilizado en prácticas anteriores. Lanza varias ejecuciones para verificar que puede resolver el problema con los problemas de las 8 ciudades gallegas (data/grafo8cidades.txt) y de las 120 ciudades estadounidenses (data/US120.txt).

❓ Pregunta 1. Explica brevemente los detalles relevantes de tu código para entender tu implementación (p.ej., estructura de tu código, funciones, implementación de operadores, etc.). Explica también cómo has realizado la verificación de tu implementación.

P4.2: Laboratorio

Realiza los laboratorios planteados a continuación para estudiar los efectos de los parámetros de la metaheurística. Para esta práctica, reporta también el coste temporal promedio de resolución.

❓ Pregunta 2. Realiza el estudio de la calidad de la solución variando el tamaño de la colonia: 1, 2, 4, 8, 16, 32, 64, 128,... ¿Qué valor recomendarías para el problema de las 120 ciudades? ¿Por qué?

❓ Pregunta 3. Ahora realiza un estudio similar variando la probabilidad de explotación q0 en el rango 0, ..., 0.95 en pasos de 0.05~0.10. ¿Qué valor recomendarías para este parámetro? ¿Por qué?

❓ Pregunta 4. Estudia la influencia de pistas de feromonas e información heurística: α=1; β=2, ..., 5. ¿Qué valor de α y β recomendarías? ¿Por qué?

❓ Pregunta 5. Finalmente, argumenta de manera crítica las diferencias y similitudes con la metaheurísticas vistas hasta el momento en las interactivas/prácticas anteriores. Discute críticamente acerca de las bondades y limitaciones de las técnicas. Por ejemplo: ¿Eres capaz de resolver instancias de diferente tamaño? ¿Con cuál estás obteniendo mejores soluciones? ¿Cuál parece tener más limitaciones en términos de tiempo de ejecución necesario? ¿Te quedarías con una de las Metaheurísticas en vista de los resultados obtenidos? ¿Cuál/es y por qué?

Apoya todas tus respuestas en datos-gráficos resultantes de tus estudios. Para la pregunta 5 no es necesario volver a tomar datos de otras prácticas, pues puedes tomar los resultados y evidencias obtenidas en prácticas anteriores. No olvides indicar qué valores has establecido para los parámetros relacionados a la condición de parada.

Importante: además de la calidad de la soluciones obtenidas, en esta práctica debes medir tiempos para tomar medidas operativas sobre el número de repeticiones que permitan realizar promedios y prescindir de manera razonada de valores en las series de ejecución que no sean computacionalmente rentables/viables con tu implementación/ordenador (p.ej., tamaños de colonia elevados pueden tomar mucho tiempo para resolver).

Pruebas pregunta 2 con actualizacion local

Pruebas pregunta 2 sin actualizacion local

Pruebas pregunta 3 con actualizacion local

Pruebas pregunta 3 sin actualizacion local

Pruebas pregunta 4 con actualizacion local

Pruebas pregunta 4 sin actualizacion local

Prueba final

Respuestas y evaluación

Recordatorio: No olvides escribir tu nombre y apellidos en la segunda celda de este documento. La respuestas a las preguntas deben venir acompañadas de las implementaciones necesarias para su respuesta.

P4.1: Implementación básica (5 puntos)

La implementación básica se evaluará mediante un cuestionario automático de evaluación. Este lo realizarás en la primera sesión tras la entrega, y se centrará en la resolución por tu parte de diversas cuestiones prácticas relacionadas con la implementación realizada, pudiendo ser necesaria la ejecución, adaptación y modificación de la misma.

Pregunta 1.

Independientemente del cuestionario automático de evaluación, considera siempre que las preguntas planteadas en el notebook deben ser respondidas también. Esas preguntas generales están diseñadas para formarte, y te servián para razonar y reflexionar sobre el tema, así como también para fomentar una discusión constructiva con los docentes en caso de dudas.

P4.2: Laboratorio (5 puntos)

El informe a elaborar no debe exceder la longitud máxima de 1200 palabras.

Aclaraciones: La evaluación de esta parte se llevará a cabo en términos de la completitud y correctitud del laboratorio implementado, así como de la calidad del propio informe, que debe ser conciso y preciso, pudiendo acompañarse de gráficas y tablas que faciliten y fundamenten la explicación e argumentación. Es muy importante explicar de manera clara, precisa y fundamentada. Se reservará hasta un punto que se asignará en términos de la calidad de la mejor solución obtenida entre el conjunto de las prácticas entregadas (es por ello que no debes olvidar marcar en tu informe muy claramente cuál ha sido tu mejor solución y con qué configuración/versión).

Pregunta 2

Pregunta 3

Pregunta 4

Pregunta 5

Respuesta 2

Para evaluar la calidad de las soluciones obtenidas al modificar el tamaño de la colonia, realizaremos tres ejecuciones del algoritmo de colonias para cada valor. De esta manera, podremos identificar tanto los costos mínimos alcanzados como los costos promedio, los cuales utilizaremos para determinar cuál sería más adecuado para abordar el problema de las 120 ciudades. Además, es necesario tener en cuenta el costo temporal asociado a cada valor, ya que a medida que la colonia aumenta en tamaño, el tiempo de ejecución del algoritmo también se incrementará. Tanto para este estudio como para los posteriores las ejecuciones se realizarán tanto con actualización de la feromona local como sin esta actualización. Los códigos y los resultados de cada prueba se pueden ver usando los enlaces que aparecerán a lo largo del laboratorio.

imagen1

Las primeras visualizaciones presentan el promedio del costo de la solución utilizando la actualización global de la feromona. En la gráfica superior, se aprecia que el tiempo medio de cada ejecución aumenta a medida que la colonia crece, como se discutió previamente. En la gráfica inferior, se destaca que con una colonia de 16 hormigas se logra un costo mínimo inferior a los demás valores. Sin embargo, al comparar los costos promedio, se observa que 64 y 128 también obtienen resultados muy favorables, siendo que 64 tiene un tiempo de ejecución menor que 128. Ver el codigo y los resultados

A continuación, se presentan las gráficas de este estudio sin la actualización local de las feromonas.

imagen1

En referencia a la gráfica superior, se observa que el tiempo de ejecución promedio es significativamente mayor, llegando a superar un minuto en el caso de una colonia de 128 hormigas. En la gráfica inferior, se evidencia que se obtienen costos considerablemente más bajos al no utilizar la actualización local, alcanzando un costo mínimo de 24,226.13 con una colonia de 16, 24,327.37 con una colonia de 128 y 24,467.47 con una colonia de 64 hormigas. Aunque los tres valores son cercanos, al analizar los resultados de cada ejecución y el costo promedio, se destaca que el valor 64 siempre logra costos por debajo de los 25,000, y su tiempo de ejecución no es excesivamente alto. En consecuencia, se recomienda utilizar el valor 64 debido a su rendimiento óptimo en términos de costo y tiempo. Ver el codigo de prueba

Respuesta 3

El próximo análisis se centrará en la probabilidad de explotación, que determina la posibilidad de que una hormiga siga una pista de feromona existente o explore nuevas rutas. Este parámetro influye significativamente en el comportamiento de las hormigas durante la construcción de soluciones. A continuación, se presenta una gráfica que ilustra el coste promedio de las soluciones utilizando 64 hormigas, variando la probabilidad de explotación.

imagen4

Como se evidencia en la gráfica superior, el coste promedio con una probabilidad de 0.95 es significativamente inferior en comparación con otros valores, alcanzando un mínimo de 27033.85 en un lapso de 28 segundos y con un coste medio de 27517,66. Por esto, a partir de ahora al hacer pruebas con actualizaciones locales utilizaremos el valor 0.95 de probabilidad de explotación. Por otro lado, el peor rendimiento se observa con un valor de 0 en la probabilidad, generando costes cercanos a los 45000 y presentando los tiempos de ejecución más elevados en toda la prueba. Para revisar el código de este experimento y obtener resultados detallados, se recomienda consultar la sección correspondiente: Pincha aquí

imagen5

En el escenario del algoritmo sin emplear actualizaciones locales, el coste promedio más reducido se registra con un valor de 23,584.33 en 24.49 segundos, utilizando una probabilidad de 0.80. Con este parámetro, se alcanza un mínimo de 23,502.50. Es interesante observar cómo los resultados obtenidos con una probabilidad de 0.9 se aproximan a los proporcionados por 0.80. Por esta razón, en futuras pruebas del algoritmo sin actualizaciones locales, optaremos por utilizar una probabilidad de 0.80. Para ver los resultados completos pincha aquí.

Respuesta 4

El último estudio que vamos a realizar se basará en comparar las diferentes combinaciones de los valores de alfa y beta. Estos parámetros son valores importantes que afectan a las decisiones que toman las hormigas en el algoritmo, el parámetro alfa (α) influye en la importancia relativa de la feromona al seleccionar el próximo nodo en la construcción de una solución. Un valor más alto de alfa da más peso a la feromona, lo que hace que las hormigas favorezcan rutas que han sido recorridas previamente por otras hormigas y, por lo tanto, tienen una concentración de feromona más alta. El parámetro beta(β) afecta a la importancia relativa de la información heurística al seleccionar el próximo nodo. Un valor más alto de beta da más peso a la información heurística, haciendo que las hormigas favorezcan rutas más cortas en términos de la información heurística.

A continuación vamos a ver gráficas de los costes medios de las distintas combinaciones, en cada gráfica se ven los cinco valores de beta para un valor fijo de alfa. Primero vemos las pruebas del algoritmo con actualizaciones locales, 64 hormigas y una probabilidad de 0.95 .

imagen85

imagen75

imagen6489257

imagen8926758749

imagen62935789

En este caso, observando las gráficas vemos que los valores minimos se acercan a 27-28 mil. Obteniendo como mínimo 27033.85 en 28.44 segundos con parámetros alfa = 1 y beta = 4. La media de los coste con estes parámetros es de 27949,21. Estos costes son mucho más altos que al hacer pruebas sin actualización local por lo que se explicará algo más de porque los parámetros de alfa y beta conviene que sean alfa más pequeño y beta más grande. Se pueden ver todos los resultados aquí.

A continuación están las gráficas de las pruebas sin actualización local.

imagen5

imagen51

imagen52

imagen53

imagen54

En el contexto del algoritmo sin actualizaciones locales, se destaca, tanto en las gráficas como en los resultados presentados, que las soluciones óptimas se obtienen cuando el parámetro alfa tiene valores bajos y el parámetro beta valores más altos. Esta elección tiene sentido, ya que da prioridad a la matriz heurística sobre la matriz de feromonas, buscando así encontrar caminos más cortos y minimizar el coste.

Se observa que los valores más bajos se alcanzan cuando se utilizan los parámetros alfa = 1 y beta = 3. En este escenario, se logra un coste medio de 24,025.66 y un mínimo de 23,910.82 en un tiempo de ejecución de 20.95 segundos.

También se encuentran resultados favorables con alfa = 1 y beta = 4 o 5, logrando valores mínimos inferiores a los obtenidos con alfa = 1 y beta = 3, como, por ejemplo, con beta = 5 se obtiene un coste mínimo de 23,597.91, aunque el coste medio es ligeramente superior.

La combinación alfa = 2 y beta = 4 también proporciona costes muy bajos, con un coste medio de 24,915.92 y un mínimo de 23,637.49.

Aunque algunas combinaciones resultaron en costes mínimos más bajos, se prioriza el análisis del coste medio. En consecuencia, sin usar actualizaciones locales, los valores más efectivos para los parámetros alfa y beta son 1 y 3.

Se pueden ver todos los resultados de las pruebas aquí.

Conclusiones del algoritmo de colonias de hormigas

Tras todos estos estudios, se ha decidido que se obtienen los mejores costes utilizando una colonia de 64 hormigas, una probabilidad de explotación de 0.80, sin usar actualizaciones locales de feromonas y con los parámetros de alfa=1 y beta=3.

Por esto, vamos a ejecutar el algoritmo con estos valores para ver cúal es el mínimo coste que podemos obtener:

Encontramos un coste menor a 23 mil y en un tiempo de ejecución de medio minuto, que es muy óptimo. Link a esta prueba aquí.

Pregunta 4

  1. Finalmente, argumenta de manera crítica las diferencias y similitudes con la metaheurísticas vistas hasta el momento en las interactivas/prácticas anteriores. Discute críticamente acerca de las bondades y limitaciones de las técnicas. Por ejemplo: ¿Eres capaz de resolver instancias de diferente tamaño? ¿Con cuál estás obteniendo mejores soluciones? ¿Cuál parece tener más limitaciones en términos de tiempo de ejecución necesario? ¿Te quedarías con una de las Metaheurísticas en vista de los resultados obtenidos? ¿Cuál/es y por qué?

A lo largo de las prácticas de la asignatura, hemos abordado la implementación de diversos algoritmos, entre ellos, el Temple Simulado, la Búsqueda Tabú, un algoritmo genético y el algoritmo de colonia de hormigas. Cada uno de estos algoritmos presenta enfoques distintos para resolver problemas y encontrar soluciones. No obstante, destaca la similitud entre el Temple Simulado y la Búsqueda Tabú, siendo esta última esencialmente una evolución mejorada del primero. En la primera práctica, se implementó un algoritmo base cuyos resultados no alcanzaron niveles óptimos, como se ilustra en la imagen a continuación.

Temple SImulado Base

En esta práctica, se introdujeron diversas mejoras con el objetivo de reducir el costo de la solución, logrando alcanzar soluciones con costos comprendidos entre 40,000 y 45,000. Aunque el algoritmo es capaz de manejar instancias de diferentes tamaños, se observa un aumento significativo en el costo temporal. Los resultados obtenidos, al menos con las mejoras implementadas, no superan a los de otros algoritmos.

Temple Simulado Mejoras

En la implementación inicial del algoritmo de Búsqueda Tabú, los costos medios obtenidos fueron de 30,906.77 con un tiempo promedio de 10 minutos y 22 segundos. Posteriormente, al aplicar mejoras, se logró reducir el costo a 25,619.983 con ejecuciones que requerían alrededor de 14 minutos. Sin embargo, esta mejora conlleva un desafío en términos de limitación temporal si se intenta aumentar el tamaño del grafo.

En relación con el algoritmo genético implementado en la práctica 3, como se evidencia en la gráfica siguiente, los resultados tampoco alcanzan la optimalidad. La media de los costos mínimos obtenidos se sitúa en 58,764.39, con un mínimo registrado de 53,968.86.

Aunque los tiempos de ejecución no son excesivos, el rendimiento no alcanza la optimización deseada.

Geneticos

Después de revisar los algoritmos previos, queda claro que la implementación del algoritmo de colonia de hormigas en esta práctica destaca significativamente. Con tiempos de ejecución de aproximadamente 30 segundos, logra alcanzar un coste de 22,983.59, el cual es el más óptimo entre todos los algoritmos implementados hasta ahora. Aunque es posible que exista alguna mejora no incorporada en la búsqueda tabú que podría generar resultados superiores, en términos de eficiencia temporal, no superaría al algoritmo de colonia de hormigas, que se posiciona como la elección preferida.